package MyBinaryTree;


import Queue.LinkQueue;
import Stack.SqStack;
import Stack.SqStackChain;

public class BinaryTreeOrder {
    // 递归的算法
    // 先序遍历  中左右
    public void preOrder(BiTreeNode root){
        // 先遍历中结点
        System.out.println(root.data +" ");
        // 遍历左节点
        preOrder(root.lchild);
        // 遍历右节点
        preOrder(root.rchild);
    }

    // 中序遍历  左中右
    public void inOrder(BiTreeNode root){
        // 左节点
        inOrder(root.lchild);
        // 中结点
        System.out.println(root.data + " ");
        // 右节点
        inOrder(root.rchild);
    }

    // 后序遍历  左右中
    public void postOrder(BiTreeNode root){
        // 遍历左节点
        preOrder(root.lchild);
        //遍历右节点
        preOrder(root.rchild);
        //遍历中结点
        System.out.println(root.data+" ");
    }

    // 利用迭代的方法完成三个遍历

    // 利用栈来完成先序遍历
    // 1.先将中结点入栈 如果栈不为空弹出
    // 2.访问左节点 如果左节点不为空则展示
    // 3.右节点入栈
    // 4.另节点置为左节点持续2,3，4步直到栈为空
    public void preOrder2(BiTreeNode root) throws Exception {
        BiTreeNode p = root;
        if(p!=null){
            // 栈链表 在链表的代码里面实现过
            SqStackChain s = new SqStackChain();
            // 入栈
            s.push(p);
            while(!s.isEmpty()){
                // 出栈
                p = (BiTreeNode) s.pop();
                System.out.println(p.data + " ");
                // 没到尾结点 就一直走
                while (p!=null){
                    // 展示左节点
                    if(p.lchild!=null) {
                        System.out.println(p.data + " ");
                    }
                    // 右节点入栈
                    if(p.rchild!=null){
                        s.push(p.rchild);
                    }
                    // 将指针指向自己的左节点
                    p = p.lchild;
                }
            }
        }
    }


    // 利用栈实现中序遍历

    // 1.将栈的中结点入栈
    // 2.在将左节点入栈直到左节点为null
    // 3.弹出栈顶结点并且访问，在将右节点入栈
    // 4.重复二三步骤直到栈为空
    public void inOrder2(BiTreeNode root) throws Exception{
        BiTreeNode p = root;
        if(p!=null){
            // 栈表
            SqStackChain s = new SqStackChain();
            // 先将中结点入栈
            s.push(p);

            // 在左节入栈找到最左节点的最小节点
            while(p.lchild!=null){
                p = p.lchild;
                s.push(p);
            }
            // 出栈节点
            p = (BiTreeNode) s.pop();
            // 展示节点
            System.out.println(p.data + " ");
            if(p.rchild!=null){
                // 入栈右节点
                s.push(p.rchild);
            }
        }
    }

    // 利用栈实现后序遍历
    // 1.将二叉树的根节点入栈，t赋值为null
    // 2.若栈非空，将栈顶节点的左节点持续入栈，直道栈顶结点的左孩子结点为空
    // 3.若栈非空，查找栈顶左节点的右孩子结点，若右孩子结点为null或者与p相等
    // 则弹出栈顶结点并且访问，同时使t指向该节点，并设置flag为true；否则将该
    // 栈顶结点的右孩子入栈设置flag为true
    public void postOrder2(BiTreeNode root) throws Exception {
        BiTreeNode p = root;
        boolean flag = true;
        BiTreeNode t = null;
        if(p!=null){
            SqStackChain s = new SqStackChain();
            // 根节点入栈
            s.push(p);
            while(!s.isEmpty()){
                // 返回栈顶元素
                p = (BiTreeNode) s.peek();
                // 将p的左节点持续入栈
                while(p.lchild != null){
                    p = p.lchild;
                    s.push(p);
                }
                while(!s.isEmpty() && flag){
                    // 左右结点都已经遍历完毕，开始访问结点
                    if(p.rchild==t || p.rchild==null){
                        System.out.println(p.data + " ");
                        flag = true;
                        t = p;
                        s.pop();
                    }else{
                        // 当 输出一个左节点时，就需要进行右节点的信息入栈
                        s.push(p.rchild);
                        flag=false;
                    }
                }
            }
        }
    }

    // 层序遍历  根节点出发 自上而下 自左而右
    // 将根节点入队列
    // 若队列非空 去除首节点访问，将队首的孩子结点入队列
    // 重复二三步知道队列空
    public void order(BiTreeNode root) throws Exception {
        BiTreeNode p = root;
        while(p!=null){
            // 构建队列
            LinkQueue q = new LinkQueue();
            q.offer(p);
            while(!q.isEmpty()){
                p = (BiTreeNode) q.poll();
                System.out.println(p.data+" ");
                if(p.lchild!=null){
                    q.offer(p.lchild);
                }
                if(p.rchild!=null){
                    q.offer(p.rchild);
                }
            }

        }


    }


}
